package com.example.leetcode.sort;

import java.util.Arrays;

/**
 * @ClassName QuickSort
 * @Description
 * 的基本思想是：
 *
 * 1．先从数列中取出一个数作为基准数。
 * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 * 3．再对左右区间重复第二步，直到各区间只有一个数。
 *
 * @Author liuzhihui
 * @Date 21/4/2021 下午 10:37
 * @Version 1.0
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] arr={101, 34, 119, 1};
        System.out.println(Arrays.toString(arr));
        quickSort1(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    //快速排序:  https://www.runoob.com/w3cnote/quick-sort.html
    // 1、确定轴值
    // 2、从右到左找第一个小于轴值的数
    private static void quick_sort(int s[], int l, int r) {
        if (l < r)
        {
            int i = l;
            int j = r;
            // 轴值,s[l]就是第一个让出来的坑位
            int x = s[l];

            while (i < j)
            {
                // 从右向左找第一个小于轴值x的数
                while(i < j && s[j] >= x)
                {
                    j--;
                }
                // 找到第一个小于轴值的数s[j]
                if(i < j) {
                    //将小于轴值的数[j]，赋值给坑位是s[i]，同时s[j]就变成一个坑位
                    s[i++] = s[j];
                }
                // 从左向右找第一个大于等于x的数
                while(i < j && s[i] < x)
                {
                    i++;
                }
                // 找到第一个大于轴值的数s[i]
                if(i < j) {
                    // 将s[i]放到坑位s[j],同时s[i]形成一个坑位
                    s[j--] = s[i];
                }
            }
            //出了循环，i==j,此时s[i]是一个坑位，将轴值填入
            s[i] = x;
            //左区间继续排序
            quick_sort(s, l, i - 1);
            //右区间继续排序
            quick_sort(s, i + 1, r);
        }
    }
    //快速排序
    private static void quickSort(int s[],int left, int right){
        if (left < right) {
            int l = left;
            int r = right;
            //轴值, 第一个坑位
            int privot = s[left];

            while(l < r){
                // 从右到左找，直到找到比轴值小的值
                while(l < r && s[r] >= privot){
                    r--;
                }
                // 找到比轴值小的值
                if(l < r){
                    // 将比轴值小的值，填进坑位，同时s[r]形成一个坑位
                    s[l] = s[r];
                    l++;
                }
                // 从左到右找，直到找到比轴值大的值
                while (l < r && s[l] < privot){
                    l++;
                }
                // 找到比轴值大的值
                if(l < r){
                    // 将比轴值大的值，填入到坑中，同时s[l]形成一个坑位
                    s[r] = s[l];
                    r--;
                }
            }
            // 推出循环时，l == r ,s[l]是一个坑位，将轴值填入
            s[l] = privot;
            // 向左区间继续排序
            quickSort(s,left,l - 1);
            // 向右区间继续排序
            quickSort(s,l + 1,right);
        }
    }
    // 快排练习
    private static void quickSort1(int s[] ,int left ,int right){
        if (left < right){
            int mid = partition(s, left, right);
            // 左区间排序
            quickSort1(s, left, mid - 1);
            // 右区间排序
            quickSort1(s, mid + 1, right);
        }
    }
    private static int partition(int[] s, int left, int right) {
        int l = left;
        int r = right;
        // 轴值，第一个坑位
        int privot = s[left];

        while(l < r){
            // 从右区间找小于轴值的值
            while(l < r && s[r] >= privot){
                r--;
            }
            //找到了，将小于轴值的值添入左区间的坑中，同时s[r]留出坑位
            if (l < r){
                s[l++] = s[r];
            }
            // 从左区间找大于轴值的值
            while(l < r && s[l] < privot){
                l++;
            }
            if (l < r){
                s[r--] = s[l];
            }
        }
        // l ==r
        s[l] = privot;
        return l;
    }
}
